package com.million.project.aiRoadSuggest;

import java.math.BigDecimal;
import java.util.*;

public class DijkstraAlgorithm {

//    public static void main(String[] args) {
//        // 创建图
//        Graph graph = createGraph();
//
//        // 选择源节点
//        GraphNode sourceNode = graph.getVertexes().get(0);
//
//        // 计算从源节点到其他节点的最短路径
//        dijkstra(graph, sourceNode);
//
//        // 打印最短路径
//        printShortestPaths(graph);
//    }

    // 创建图
    public static Graph createGraph() {
        Graph graph = new Graph(5); // 5 个节点的图

        // 添加节点
        GraphNode nodeA = new GraphNode(0, "122.3", "122.6", "2");
        GraphNode nodeB = new GraphNode(1, "B", "0", "0");
        GraphNode nodeC = new GraphNode(2, "C", "0", "0");
        GraphNode nodeD = new GraphNode(3, "D", "0", "0");
        GraphNode nodeE = new GraphNode(4, "E", "0", "0");

        graph.getVertexes().add(nodeA);
        graph.getVertexes().add(nodeB);
        graph.getVertexes().add(nodeC);
        graph.getVertexes().add(nodeD);
        graph.getVertexes().add(nodeE);

//        // 添加边
//        addEdge(nodeA, nodeB, 1, new BigDecimal("10"));
//        addEdge(nodeA, nodeC, 2, new BigDecimal("15"));
//        addEdge(nodeB, nodeC, 1, new BigDecimal("20"));
//        addEdge(nodeC, nodeD, 1, new BigDecimal("25"));
//        addEdge(nodeB, nodeD, 2, new BigDecimal("30"));
//        addEdge(nodeD, nodeE, 1, new BigDecimal("35"));

        return graph;
    }

    // 添加边
    public static void addEdge(GraphNode from, GraphNode to, float roadLength,float roadCost) {
        GraphEdge edge = new GraphEdge(202,roadLength, roadCost,3,from,to); // 限行车辆类型暂时设为3
        from.setFirst(edge);
    }

    /*
    // Dijkstra算法实现
    public static void dijkstra(Graph graph, GraphNode sourceNode) {
        PriorityQueue<GraphNode> priorityQueue = new PriorityQueue<>(Comparator.comparingDouble(GraphNode::getDistance));
        Set<GraphNode> visited = new HashSet<>();

        // 初始化
        for (GraphNode node : graph.getVertexes()) {
            if (node == sourceNode) {
                node.setDistance(0);
            } else {
                node.setDistance(Double.POSITIVE_INFINITY);
            }
            priorityQueue.add(node);
        }

        while (!priorityQueue.isEmpty()) {
            GraphNode current = priorityQueue.poll();
            visited.add(current);

            for (GraphEdge edge = current.getFirst(); edge != null; edge = edge.getNext()) {
                GraphNode neighbor = edge.getDestinationNode();
                if (!visited.contains(neighbor)) {
                    double distanceThroughCurrent = current.getDistance() + edge.getRoadLength();
                    if (distanceThroughCurrent < neighbor.getDistance()) {
                        priorityQueue.remove(neighbor);
                        neighbor.setDistance(distanceThroughCurrent);
                        neighbor.setPrevious(current);
                        priorityQueue.add(neighbor);
                    }
                }
            }
        }
    }

    // 打印最短路径
    public static void printShortestPaths(Graph graph) {
        for (GraphNode node : graph.getVertexes()) {
            List<GraphNode> path = new ArrayList<>();
            for (GraphNode current = node; current != null; current = current.getPrevious()) {
                path.add(current);
            }
            Collections.reverse(path);
            System.out.print("Shortest path from source to " + node.getCityName() + ": ");
            for (GraphNode n : path) {
                System.out.print(n.getCityName() + " ");
            }
            System.out.println(", distance: " + node.getDistance());
        }
    }
    */

}

